Search Results

Documents authored by Albers, Susanne

Document
DOI: 10.4230/LIPIcs.ESA.2022.4
Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities

Authors: Susanne Albers and Sebastian Schubert

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We study the b-matching problem in bipartite graphs G = (S,R,E). Each vertex s ∈ S is a server with individual capacity b_s. The vertices r ∈ R are requests that arrive online and must be assigned instantly to an eligible server. The goal is to maximize the size of the constructed matching. We assume that G is a (k,d)-graph [J. Naor and D. Wajc, 2018], where k specifies a lower bound on the degree of each server and d is an upper bound on the degree of each request. This setting models matching problems in timely applications. We present tight upper and lower bounds on the performance of deterministic online algorithms. In particular, we develop a new online algorithm via a primal-dual analysis. The optimal competitive ratio tends to 1, for arbitrary k ≥ d, as the server capacities increase. Hence, nearly optimal solutions can be computed online. Our results also hold for the vertex-weighted problem extension, and thus for AdWords and auction problems in which each bidder issues individual, equally valued bids. Our bounds improve the previous best competitive ratios. The asymptotic competitiveness of 1 is a significant improvement over the previous factor of 1-1/e^{k/d}, for the interesting range where k/d ≥ 1 is small. Recall that 1-1/e ≈ 0.63. Matching problems that admit a competitive ratio arbitrarily close to 1 are rare. Prior results rely on randomization or probabilistic input models.
Cite as

Susanne Albers and Sebastian Schubert. Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:LIPIcs.ESA.2022.4,
  author =	{Albers, Susanne and Schubert, Sebastian},
  title =	{{Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.4},
  URN =		{urn:nbn:de:0030-drops-169420},
  doi =		{10.4230/LIPIcs.ESA.2022.4},
  annote =	{Keywords: online algorithms, deterministic algorithms, primal-dual analysis, b-matching, bounded-degree graph, variable vertex capacities, unweighted matching, vertex-weighted matching}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.52
Machine Covering in the Random-Order Model

Authors: Susanne Albers, Waldo Gálvez, and Maximilian Janke

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
In the Online Machine Covering problem jobs, defined by their sizes, arrive one by one and have to be assigned to m parallel and identical machines, with the goal of maximizing the load of the least-loaded machine. Unfortunately, the classical model allows only fairly pessimistic performance guarantees: The best possible deterministic ratio of m is achieved by the Greedy-strategy, and the best known randomized algorithm has competitive ratio Õ(√m) which cannot be improved by more than a logarithmic factor. Modern results try to mitigate this by studying semi-online models, where additional information about the job sequence is revealed in advance or extra resources are provided to the online algorithm. In this work we study the Machine Covering problem in the recently popular random-order model. Here no extra resources are present, but instead the adversary is weakened in that it can only decide upon the input set while jobs are revealed uniformly at random. It is particularly relevant to Machine Covering where lower bounds are usually associated to highly structured input sequences. We first analyze Graham’s Greedy-strategy in this context and establish that its competitive ratio decreases slightly to Θ(m/(log(m))) which is asymptotically tight. Then, as our main result, we present an improved Õ(∜m)-competitive algorithm for the problem. This result is achieved by exploiting the extra information coming from the random order of the jobs, using sampling techniques to devise an improved mechanism to distinguish jobs that are relatively large from small ones. We complement this result with a first lower bound showing that no algorithm can have a competitive ratio of O(log(m)/{log log(m)}) in the random-order model. This lower bound is achieved by studying a novel variant of the Secretary problem, which could be of independent interest.
Cite as

Susanne Albers, Waldo Gálvez, and Maximilian Janke. Machine Covering in the Random-Order Model. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 52:1-52:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:LIPIcs.ISAAC.2021.52,
  author =	{Albers, Susanne and G\'{a}lvez, Waldo and Janke, Maximilian},
  title =	{{Machine Covering in the Random-Order Model}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{52:1--52:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.52},
  URN =		{urn:nbn:de:0030-drops-154858},
  doi =		{10.4230/LIPIcs.ISAAC.2021.52},
  annote =	{Keywords: Machine Covering, Online Algorithm, Random-Order, Competitive Analysis, Scheduling}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2021.6
Scheduling in the Secretary Model

Authors: Susanne Albers and Maximilian Janke

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract
This paper studies online makespan minimization in the secretary model. Jobs, specified by their processing times, are presented in a uniformly random order. The input size n is known in advance. An online algorithm has to non-preemptively assign each job permanently and irrevocably to one of m parallel and identical machines such that the expected time it takes to process them all, the makespan, is minimized. We give two deterministic algorithms. First, a straightforward adaptation of the semi-online strategy Light Load [Albers and Hellwig, 2012] provides a very simple approach retaining its competitive ratio of 1.75. A new and sophisticated algorithm is 1.535-competitive. These competitive ratios are not only obtained in expectation but, in fact, for all but a very tiny fraction of job orders. Classically, online makespan minimization only considers the worst-case order. Here, no competitive ratio below 1.885 for deterministic algorithms and 1.581 using randomization is possible. The best randomized algorithm so far is 1.916-competitive. Our results show that classical worst-case orders are quite rare and pessimistic for many applications. We complement our results by providing first lower bounds. A competitive ratio obtained on nearly all possible job orders must be at least 1.257. This implies a lower bound of 1.043 for both deterministic and randomized algorithms in the general model.
Cite as

Susanne Albers and Maximilian Janke. Scheduling in the Secretary Model. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 6:1-6:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:LIPIcs.FSTTCS.2021.6,
  author =	{Albers, Susanne and Janke, Maximilian},
  title =	{{Scheduling in the Secretary Model}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{6:1--6:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.6},
  URN =		{urn:nbn:de:0030-drops-155172},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.6},
  annote =	{Keywords: Scheduling, makespan minimization, online algorithm, competitive analysis, lower bound, random-order, secretary problem}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.2
Optimal Algorithms for Online b-Matching with Variable Vertex Capacities

Authors: Susanne Albers and Sebastian Schubert

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract
We study the b-matching problem, which generalizes classical online matching introduced by Karp, Vazirani and Vazirani (STOC 1990). Consider a bipartite graph G = (S ̇∪ R,E). Every vertex s ∈ S is a server with a capacity b_s, indicating the number of possible matching partners. The vertices r ∈ R are requests that arrive online and must be matched immediately to an eligible server. The goal is to maximize the cardinality of the constructed matching. In contrast to earlier work, we study the general setting where servers may have arbitrary, individual capacities. We prove that the most natural and simple online algorithms achieve optimal competitive ratios. As for deterministic algorithms, we give a greedy algorithm RelativeBalance and analyze it by extending the primal-dual framework of Devanur, Jain and Kleinberg (SODA 2013). In the area of randomized algorithms we study the celebrated Ranking algorithm by Karp, Vazirani and Vazirani. We prove that the original Ranking strategy, simply picking a random permutation of the servers, achieves an optimal competitiveness of 1-1/e, independently of the server capacities. Hence it is not necessary to resort to a reduction, replacing every server s by b_s vertices of unit capacity and to then run Ranking on this graph with ∑_{s ∈ S} b_s vertices on the left-hand side. From a theoretical point of view our result explores the power of randomization and strictly limits the amount of required randomness. From a practical point of view it leads to more efficient allocation algorithms. Technically, we show that the primal-dual framework of Devanur, Jain and Kleinberg cannot establish a competitiveness better than 1/2 for the original Ranking algorithm, choosing a permutation of the servers. Therefore, we formulate a new configuration LP for the b-matching problem and then conduct a primal-dual analysis. We extend this analysis approach to the vertex-weighted b-matching problem. Specifically, we show that the algorithm PerturbedGreedy by Aggarwal, Goel, Karande and Mehta (SODA 2011), again with a sole randomization over the set of servers, is (1-1/e)-competitive. Together with recent work by Huang and Zhang (STOC 2020), our results demonstrate that configuration LPs can be strictly stronger than standard LPs in the analysis of more complex matching problems.
Cite as

Susanne Albers and Sebastian Schubert. Optimal Algorithms for Online b-Matching with Variable Vertex Capacities. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 2:1-2:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:LIPIcs.APPROX/RANDOM.2021.2,
  author =	{Albers, Susanne and Schubert, Sebastian},
  title =	{{Optimal Algorithms for Online b-Matching with Variable Vertex Capacities}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{2:1--2:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.2},
  URN =		{urn:nbn:de:0030-drops-146957},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.2},
  annote =	{Keywords: Online algorithms, primal-dual analysis, configuration LP, b-matching, variable vertex capacities, unweighted matching, vertex-weighted matching}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.7
Best Fit Bin Packing with Random Order Revisited

Authors: Susanne Albers, Arindam Khan, and Leon Ladewig

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
Best Fit is a well known online algorithm for the bin packing problem, where a collection of one-dimensional items has to be packed into a minimum number of unit-sized bins. In a seminal work, Kenyon [SODA 1996] introduced the (asymptotic) random order ratio as an alternative performance measure for online algorithms. Here, an adversary specifies the items, but the order of arrival is drawn uniformly at random. Kenyon’s result establishes lower and upper bounds of 1.08 and 1.5, respectively, for the random order ratio of Best Fit. Although this type of analysis model became increasingly popular in the field of online algorithms, no progress has been made for the Best Fit algorithm after the result of Kenyon. We study the random order ratio of Best Fit and tighten the long-standing gap by establishing an improved lower bound of 1.10. For the case where all items are larger than 1/3, we show that the random order ratio converges quickly to 1.25. It is the existence of such large items that crucially determines the performance of Best Fit in the general case. Moreover, this case is closely related to the classical maximum-cardinality matching problem in the fully online model. As a side product, we show that Best Fit satisfies a monotonicity property on such instances, unlike in the general case. In addition, we initiate the study of the absolute random order ratio for this problem. In contrast to asymptotic ratios, absolute ratios must hold even for instances that can be packed into a small number of bins. We show that the absolute random order ratio of Best Fit is at least 1.3. For the case where all items are larger than 1/3, we derive upper and lower bounds of 21/16 and 1.2, respectively.
Cite as

Susanne Albers, Arindam Khan, and Leon Ladewig. Best Fit Bin Packing with Random Order Revisited. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:LIPIcs.MFCS.2020.7,
  author =	{Albers, Susanne and Khan, Arindam and Ladewig, Leon},
  title =	{{Best Fit Bin Packing with Random Order Revisited}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.7},
  URN =		{urn:nbn:de:0030-drops-127300},
  doi =		{10.4230/LIPIcs.MFCS.2020.7},
  annote =	{Keywords: Online bin packing, random arrival order, probabilistic analysis}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.68
Scheduling in the Random-Order Model

Authors: Susanne Albers and Maximilian Janke

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
Makespan minimization on identical machines is a fundamental problem in online scheduling. The goal is to assign a sequence of jobs to m identical parallel machines so as to minimize the maximum completion time of any job. Already in the 1960s, Graham showed that Greedy is (2-1/m)-competitive [Graham, 1966]. The best deterministic online algorithm currently known achieves a competitive ratio of 1.9201 [Fleischer and Wahl, 2000]. No deterministic online strategy can obtain a competitiveness smaller than 1.88 [Rudin III, 2001]. In this paper, we study online makespan minimization in the popular random-order model, where the jobs of a given input arrive as a random permutation. It is known that Greedy does not attain a competitive factor asymptotically smaller than 2 in this setting [Osborn and Torng, 2008]. We present the first improved performance guarantees. Specifically, we develop a deterministic online algorithm that achieves a competitive ratio of 1.8478. The result relies on a new analysis approach. We identify a set of properties that a random permutation of the input jobs satisfies with high probability. Then we conduct a worst-case analysis of our algorithm, for the respective class of permutations. The analysis implies that the stated competitiveness holds not only in expectation but with high probability. Moreover, it provides mathematical evidence that job sequences leading to higher performance ratios are extremely rare, pathological inputs. We complement the results by lower bounds for the random-order model. We show that no deterministic online algorithm can achieve a competitive ratio smaller than 4/3. Moreover, no deterministic online algorithm can attain a competitiveness smaller than 3/2 with high probability.
Cite as

Susanne Albers and Maximilian Janke. Scheduling in the Random-Order Model. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 68:1-68:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:LIPIcs.ICALP.2020.68,
  author =	{Albers, Susanne and Janke, Maximilian},
  title =	{{Scheduling in the Random-Order Model}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{68:1--68:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.68},
  URN =		{urn:nbn:de:0030-drops-124750},
  doi =		{10.4230/LIPIcs.ICALP.2020.68},
  annote =	{Keywords: Scheduling, makespan minimization, online algorithm, competitive analysis, lower bound, random-order}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.SWAT.2020
LIPIcs, Volume 162, SWAT 2020, Complete Volume

Authors: Susanne Albers

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
LIPIcs, Volume 162, SWAT 2020, Complete Volume
Cite as

17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 1-606, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{albers:LIPIcs.SWAT.2020,
  title =	{{LIPIcs, Volume 162, SWAT 2020, Complete Volume}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{1--606},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020},
  URN =		{urn:nbn:de:0030-drops-122469},
  doi =		{10.4230/LIPIcs.SWAT.2020},
  annote =	{Keywords: LIPIcs, Volume 162, SWAT 2020, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.SWAT.2020.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Susanne Albers

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{albers:LIPIcs.SWAT.2020.0,
  author =	{Albers, Susanne},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{0:i--0:x},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.0},
  URN =		{urn:nbn:de:0030-drops-122476},
  doi =		{10.4230/LIPIcs.SWAT.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.12
New Bounds for Randomized List Update in the Paid Exchange Model

Authors: Susanne Albers and Maximilian Janke

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
We study the fundamental list update problem in the paid exchange model P^d. This cost model was introduced by Manasse, McGeoch and Sleator [M.S. Manasse et al., 1988] and Reingold, Westbrook and Sleator [N. Reingold et al., 1994]. Here the given list of items may only be rearranged using paid exchanges; each swap of two adjacent items in the list incurs a cost of d. Free exchanges of items are not allowed. The model is motivated by the fact that, when executing search operations on a data structure, key comparisons are less expensive than item swaps. We develop a new randomized online algorithm that achieves an improved competitive ratio against oblivious adversaries. For large d, the competitiveness tends to 2.2442. Technically, the analysis of the algorithm relies on a new approach of partitioning request sequences and charging expected cost. Furthermore, we devise lower bounds on the competitiveness of randomized algorithms against oblivious adversaries. No such lower bounds were known before. Specifically, we prove that no randomized online algorithm can achieve a competitive ratio smaller than 2 in the partial cost model, where an access to the i-th item in the current list incurs a cost of i-1 rather than i. All algorithms proposed in the literature attain their competitiveness in the partial cost model. Furthermore, we show that no randomized online algorithm can achieve a competitive ratio smaller than 1.8654 in the standard full cost model. Again the lower bounds hold for large d.
Cite as

Susanne Albers and Maximilian Janke. New Bounds for Randomized List Update in the Paid Exchange Model. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:LIPIcs.STACS.2020.12,
  author =	{Albers, Susanne and Janke, Maximilian},
  title =	{{New Bounds for Randomized List Update in the Paid Exchange Model}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.12},
  URN =		{urn:nbn:de:0030-drops-118735},
  doi =		{10.4230/LIPIcs.STACS.2020.12},
  annote =	{Keywords: self-organizing lists, online algorithm, competitive analysis, lower bound}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.18
New Results for the k-Secretary Problem

Authors: Susanne Albers and Leon Ladewig

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
Suppose that n numbers arrive online in random order and the goal is to select k of them such that the expected sum of the selected items is maximized. The decision for any item is irrevocable and must be made on arrival without knowing future items. This problem is known as the k-secretary problem, which includes the classical secretary problem with the special case k=1. It is well-known that the latter problem can be solved by a simple algorithm of competitive ratio 1/e which is asymptotically optimal. When k is small, only for k=2 does there exist an algorithm beating the threshold of 1/e [Chan et al. SODA 2015]. The algorithm relies on an involved selection policy. Moreover, there exist results when k is large [Kleinberg SODA 2005]. In this paper we present results for the k-secretary problem, considering the interesting and relevant case that k is small. We focus on simple selection algorithms, accompanied by combinatorial analyses. As a main contribution we propose a natural deterministic algorithm designed to have competitive ratios strictly greater than 1/e for small k >= 2. This algorithm is hardly more complex than the elegant strategy for the classical secretary problem, optimal for k=1, and works for all k >= 1. We explicitly compute its competitive ratios for 2 <= k <= 100, ranging from 0.41 for k=2 to 0.75 for k=100. Moreover, we show that an algorithm proposed by Babaioff et al. [APPROX 2007] has a competitive ratio of 0.4168 for k=2, implying that the previous analysis was not tight. Our analysis reveals a surprising combinatorial property of this algorithm, which might be helpful for a tight analysis of this algorithm for general k.
Cite as

Susanne Albers and Leon Ladewig. New Results for the k-Secretary Problem. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 18:1-18:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:LIPIcs.ISAAC.2019.18,
  author =	{Albers, Susanne and Ladewig, Leon},
  title =	{{New Results for the k-Secretary Problem}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{18:1--18:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.18},
  URN =		{urn:nbn:de:0030-drops-115142},
  doi =		{10.4230/LIPIcs.ISAAC.2019.18},
  annote =	{Keywords: Online algorithms, secretary problem, random order model}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.22
Improved Online Algorithms for Knapsack and GAP in the Random Order Model

Authors: Susanne Albers, Arindam Khan, and Leon Ladewig

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
The knapsack problem is one of the classical problems in combinatorial optimization: Given a set of items, each specified by its size and profit, the goal is to find a maximum profit packing into a knapsack of bounded capacity. In the online setting, items are revealed one by one and the decision, if the current item is packed or discarded forever, must be done immediately and irrevocably upon arrival. We study the online variant in the random order model where the input sequence is a uniform random permutation of the item set. We develop a randomized (1/6.65)-competitive algorithm for this problem, outperforming the current best algorithm of competitive ratio 1/8.06 [Kesselheim et al. SIAM J. Comp. 47(5)]. Our algorithm is based on two new insights: We introduce a novel algorithmic approach that employs two given algorithms, optimized for restricted item classes, sequentially on the input sequence. In addition, we study and exploit the relationship of the knapsack problem to the 2-secretary problem. The generalized assignment problem (GAP) includes, besides the knapsack problem, several important problems related to scheduling and matching. We show that in the same online setting, applying the proposed sequential approach yields a (1/6.99)-competitive randomized algorithm for GAP. Again, our proposed algorithm outperforms the current best result of competitive ratio 1/8.06 [Kesselheim et al. SIAM J. Comp. 47(5)].
Cite as

Susanne Albers, Arindam Khan, and Leon Ladewig. Improved Online Algorithms for Knapsack and GAP in the Random Order Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 22:1-22:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:LIPIcs.APPROX-RANDOM.2019.22,
  author =	{Albers, Susanne and Khan, Arindam and Ladewig, Leon},
  title =	{{Improved Online Algorithms for Knapsack and GAP in the Random Order Model}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{22:1--22:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.22},
  URN =		{urn:nbn:de:0030-drops-112376},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.22},
  annote =	{Keywords: Online algorithms, knapsack problem, random order model}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.7
Tight Bounds for Online Coloring of Basic Graph Classes

Authors: Susanne Albers and Sebastian Schraink

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
We resolve a number of long-standing open problems in online graph coloring. More specifically, we develop tight lower bounds on the performance of online algorithms for fundamental graph classes. An important contribution is that our bounds also hold for randomized online algorithms, for which hardly any results were known. Technically, we construct lower bounds for chordal graphs. The constructions then allow us to derive results on the performance of randomized online algorithms for the following further graph classes: trees, planar, bipartite, inductive, bounded-treewidth and disk graphs. It shows that the best competitive ratio of both deterministic and randomized online algorithms is Theta(log n), where n is the number of vertices of a graph. Furthermore, we prove that this guarantee cannot be improved if an online algorithm has a lookahead of size O(n/log n) or access to a reordering buffer of size n^(1-epsilon), for any 0 < epsilon <= 1. A consequence of our results is that, for all of the above mentioned graph classes except bipartite graphs, the natural First Fit coloring algorithm achieves an optimal performance, up to constant factors, among deterministic and randomized online algorithms.
Cite as

Susanne Albers and Sebastian Schraink. Tight Bounds for Online Coloring of Basic Graph Classes. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:LIPIcs.ESA.2017.7,
  author =	{Albers, Susanne and Schraink, Sebastian},
  title =	{{Tight Bounds for Online Coloring of Basic Graph Classes}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.7},
  URN =		{urn:nbn:de:0030-drops-78268},
  doi =		{10.4230/LIPIcs.ESA.2017.7},
  annote =	{Keywords: graph coloring, online algorithms, lower bounds, randomization}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.10
On the Value of Penalties in Time-Inconsistent Planning

Authors: Susanne Albers and Dennis Kraft

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
People tend to behave inconsistently over time due to an inherent present bias. As this may impair performance, social and economic settings need to be adapted accordingly. Common tools to reduce the impact of time-inconsistent behavior are penalties and prohibition. Such tools are called commitment devices. In recent work Kleinberg and Oren [EC, 2014] connect the design of a prohibition-based commitment device to a combinatorial problem in which edges are removed from a task graph G with n nodes. However, this problem is NP-hard to approximate within a ratio less than n^(1/2)/3 [Albers and Kraft, WINE, 2016]. To address this issue, we propose a penalty-based commitment device that does not delete edges, but raises their cost. The benefits of our approach are twofold. On the conceptual side, we show that penalties are up to 1/beta times more efficient than prohibition, where 0 < beta <= 1 parameterizes the present bias. On the computational side, we improve approximability by presenting a 2-approximation algorithm for allocating penalties. To complement this result, we prove that optimal penalties are NP-hard to approximate within a ratio of 1.08192.
Cite as

Susanne Albers and Dennis Kraft. On the Value of Penalties in Time-Inconsistent Planning. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 10:1-10:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:LIPIcs.ICALP.2017.10,
  author =	{Albers, Susanne and Kraft, Dennis},
  title =	{{On the Value of Penalties in Time-Inconsistent Planning}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{10:1--10:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.10},
  URN =		{urn:nbn:de:0030-drops-73876},
  doi =		{10.4230/LIPIcs.ICALP.2017.10},
  annote =	{Keywords: approximation algorithms, behavioral economics, commitment devices, computational complexity, time-inconsistent preferences}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.SOCG.2015.872
Modeling Real-World Data Sets (Invited Talk)

Authors: Susanne Albers

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
Traditionally, the performance of algorithms is evaluated using worst-case analysis. For a number of problems, this type of analysis gives overly pessimistic results: Worst-case inputs are rather artificial and do not occur in practical applications. In this lecture we review some alternative analysis approaches leading to more realistic and robust performance evaluations. Specifically, we focus on the approach of modeling real-world data sets. We report on two studies performed by the author for the problems of self-organizing search and paging. In these settings real data sets exhibit locality of reference. We devise mathematical models capturing locality. Furthermore, we present combined theoretical and experimental analyses in which the theoretically proven and experimentally observed performance guarantees match up to very small relative errors.
Cite as

Susanne Albers. Modeling Real-World Data Sets (Invited Talk). In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, p. 872, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{albers:LIPIcs.SOCG.2015.872,
  author =	{Albers, Susanne},
  title =	{{Modeling Real-World Data Sets}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{872--872},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.872},
  URN =		{urn:nbn:de:0030-drops-50865},
  doi =		{10.4230/LIPIcs.SOCG.2015.872},
  annote =	{Keywords: Worst-case analysis, real data sets, locality of reference, paging, self-organizing lists}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.STACS.2008
LIPIcs, Volume 1, STACS'08, Complete Volume

Authors: Susanne Albers and Pascal Weil

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
LIPIcs, Volume 1, STACS'08, Complete Volume
Cite as

25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Proceedings{albers_et_al:LIPIcs.STACS.2008,
  title =	{{LIPIcs, Volume 1, STACS'08, Complete Volume}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008},
  URN =		{urn:nbn:de:0030-drops-40958},
  doi =		{10.4230/LIPIcs.STACS.2008},
  annote =	{Keywords: LIPIcs, Volume 1, STACS'08, Complete Volume}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.STACS.2009
LIPIcs, Volume 3, STACS'09, Complete Volume

Authors: Susanne Albers and Jean-Yves Marion

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
LIPIcs, Volume 3, STACS'09, Complete Volume
Cite as

26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Proceedings{albers_et_al:LIPIcs.STACS.2009,
  title =	{{LIPIcs, Volume 3, STACS'09, Complete Volume}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009},
  URN =		{urn:nbn:de:0030-drops-40975},
  doi =		{10.4230/LIPIcs.STACS.2009},
  annote =	{Keywords: LIPIcs, Volume 3, STACS'09, Complete Volume}
}
Document
DOI: 10.4230/DagRep.3.3.24
Scheduling (Dagstuhl Seminar 13111)

Authors: Susanne Albers, Onno J. Boxma, and Kirk Pruhs

Published in: Dagstuhl Reports, Volume 3, Issue 3 (2013)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13111 "Scheduling". The primary objective of the seminar is to facilitate dialog and collaboration between researchers in two different mathematically-oriented scheduling research communities, the stochastic scheduling and queuing community, and the worst-case approximation scheduling community.
Cite as

Susanne Albers, Onno J. Boxma, and Kirk Pruhs. Scheduling (Dagstuhl Seminar 13111). In Dagstuhl Reports, Volume 3, Issue 3, pp. 24-50, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{albers_et_al:DagRep.3.3.24,
  author =	{Albers, Susanne and Boxma, Onno J. and Pruhs, Kirk},
  title =	{{Scheduling (Dagstuhl Seminar 13111)}},
  pages =	{24--50},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{3},
  editor =	{Albers, Susanne and Boxma, Onno J. and Pruhs, Kirk},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.3.3.24},
  URN =		{urn:nbn:de:0030-drops-40244},
  doi =		{10.4230/DagRep.3.3.24},
  annote =	{Keywords: Scheduling, Algorithms, Stochastic, Optimization, Queuing}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSTTCS.2011.1
Energy-Efficient Algorithms (Invited Talk)

Authors: Susanne Albers

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Abstract
This presentation surveys algorithmic techniques for energy savings. We address power-down as well as dynamic speed scaling mechanisms.
Cite as

Susanne Albers. Energy-Efficient Algorithms (Invited Talk). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{albers:LIPIcs.FSTTCS.2011.1,
  author =	{Albers, Susanne},
  title =	{{Energy-Efficient Algorithms}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{1--2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.1},
  URN =		{urn:nbn:de:0030-drops-33380},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.1},
  annote =	{Keywords: energy efficiency, power-down mechanisms, dynamic speed scaling, offline algorithm, online algorithm}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.1
Algorithms for Dynamic Speed Scaling

Authors: Susanne Albers

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
Many modern microprocessors allow the speed/frequency to be set dynamically. The general goal is to execute a sequence of jobs on a variable-speed processor so as to minimize energy consumption. This paper surveys algorithmic results on dynamic speed scaling. We address settings where (1) jobs have strict deadlines and (2) job flow times are to be minimized.
Cite as

Susanne Albers. Algorithms for Dynamic Speed Scaling. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{albers:LIPIcs.STACS.2011.1,
  author =	{Albers, Susanne},
  title =	{{Algorithms for Dynamic Speed Scaling}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{1--11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.1},
  URN =		{urn:nbn:de:0030-drops-29954},
  doi =		{10.4230/LIPIcs.STACS.2011.1},
  annote =	{Keywords: competitive analysis, energy-efficiency, flow time, job deadline, offline algorithm, online algorithm, response time, scheduling, variable-speed proce}
}
Document
DOI: 10.4230/DagSemProc.10071.1
10071 Abstracts Collection – Scheduling

Authors: Susanne Albers, Sanjoy K. Baruah, Rolf H. Möhring, and Kirk Pruhs

Published in: Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010)

Abstract
From 14.02. to 19.02.2010, the Dagstuhl Seminar 10071 ``Scheduling '' was held in Schloss Dagstuhl-Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Susanne Albers, Sanjoy K. Baruah, Rolf H. Möhring, and Kirk Pruhs. 10071 Abstracts Collection – Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:DagSemProc.10071.1,
  author =	{Albers, Susanne and Baruah, Sanjoy K. and M\"{o}hring, Rolf  H. and Pruhs, Kirk},
  title =	{{10071 Abstracts Collection – Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.1},
  URN =		{urn:nbn:de:0030-drops-25479},
  doi =		{10.4230/DagSemProc.10071.1},
  annote =	{Keywords: Scheduling, real-time, complexity, approximation algorithms}
}
Document
DOI: 10.4230/DagSemProc.10071.2
10071 Executive Summary – Scheduling

Authors: Susanne Albers, Sanjoy K. Baruah, Rolf H. Möhring, and Kirk Pruhs

Published in: Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010)

Abstract
The primary objectives of this seminar were to bring together leading researchers working on scheduling problems in three different research communities – operations research, theoretical computer science, and real-time systems – to expose each community to the important problems addressed by the other communities; to enable and encourage cooperation among the researchers; and to facilitate a transfer of solution techniques from each community to the others.
Cite as

Susanne Albers, Sanjoy K. Baruah, Rolf H. Möhring, and Kirk Pruhs. 10071 Executive Summary – Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:DagSemProc.10071.2,
  author =	{Albers, Susanne and Baruah, Sanjoy K. and M\"{o}hring, Rolf  H. and Pruhs, Kirk},
  title =	{{10071 Executive Summary – Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.2},
  URN =		{urn:nbn:de:0030-drops-25417},
  doi =		{10.4230/DagSemProc.10071.2},
  annote =	{Keywords: Scheduling, real-time, complexity, approximation algorithms}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.STACS.2009.1858
Preface -- 26th International Symposium on Theoretical Aspects of Computer Science

Authors: Susanne Albers and Jean-Yves Marion

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
The interest in STACS has remained at a high level over the past years. The STACS 2009 call for papers led to over 280 submissions from 41 countries. Each paper was assigned to three program committee members. The program committee held a two-week electronic meeting at the beginning of November and selected 54 papers. As co-chairs of the program committee, we would like to sincerely thank its members and the many external referees for their valuable work. The overall very high quality of the submissions made the selection a difficult task. We would like to express our thanks to the three invited speakers, Monika Henzinger, Jean-Eric Pin and Nicole Schweikardt, for their contributions to the proceedings. Special thanks are due to A. Voronkov for his EasyChair software (www.easychair.org). Moreover we would like to thank Sonja Lauer for preparing the conference proceedings and continuous help throughout the conference organization. For the second time this year's STACS proceedings are published in electronic form. A printed version was also available at the conference, with ISBN 978-3-939897-09-5. The electronic proceedings are available through several portals, and in particular through HAL and DROPS. HAL is an electronic repository managed by several French research agencies, and DROPS is the Dagstuhl Research Online Publication Server. We want to thank both these servers for hosting the proceedings of STACS and guaranteeing them perennial availability. The rights on the articles in the proceedings are kept with the authors and the papers are available freely, under a Creative Commons license (seewww.stacs-conf.org/faq.html for more details).
Cite as

26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. i-vii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:LIPIcs.STACS.2009.1858,
  author =	{Albers, Susanne and Marion, Jean-Yves},
  title =	{{Preface -- 26th International Symposium on Theoretical Aspects of Computer Science}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{i--vii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1858},
  URN =		{urn:nbn:de:0030-drops-18584},
  doi =		{10.4230/LIPIcs.STACS.2009.1858},
  annote =	{Keywords: Symposium, Theoretical computer science, Algorithms and data structures, Automata and formal languages, Computational and structural complex}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.STACS.2008.1378
Abstracts Collection -- 25th International Symposium on Theoretical Aspects of Computer Science

Authors: Susanne Albers and Pascal Weil

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
The Symposium on Theoretical Aspects of Computer Science (STACS) is held alternately in France and in Germany. The conference of February 21-23, 2008, held in Bordeaux, is the 25th in this series. Previous meetings took place in Paris (1984), Saarbr\"{u}cken (1985), Orsay (1986), Passau (1987), Bordeaux (1988), Paderborn (1989), Rouen (1990), Hamburg (1991), Cachan (1992), W\"{u}rzburg 1993), Caen (1994), M\"{u}nchen (1995), Grenoble (1996), L\"{u}beck (1997), Paris (1998), Trier (1999), Lille (2000), Dresden (2001), Antibes (2002), Berlin (2003), Montpellier (2004), Stuttgart (2005), Marseille (2006) and Aachen (2007).
Cite as

25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. i-xxviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:LIPIcs.STACS.2008.1378,
  author =	{Albers, Susanne and Weil, Pascal},
  title =	{{Abstracts Collection -- 25th International Symposium on Theoretical Aspects of Computer Science}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{i--xxviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1378},
  URN =		{urn:nbn:de:0030-drops-13780},
  doi =		{10.4230/LIPIcs.STACS.2008.1378},
  annote =	{Keywords: Symposium, theoretical computer science, algorithms and data structures, automata and formal languages, computational and structural complexity, logic in computer science, applications}
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1326
Preface -- 25th International Symposium on Theoretical Aspects of Computer Science

Authors: Susanne Albers and Pascal Weil

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
The interest in STACS has remained at a high level over the past years. The STACS 2008 call for papers led to approximately 200 submissions from 38 countries. Each was assigned to at least three program committee members. The program committee held a 2-week long electronic meeting at the end of November, to select 54 papers. As co-chairs of this committee, we would like to sincerely thank its members and the many external referees for the valuable work they put into the reviewing process. The overall very high quality of the papers that were submitted to the conference made this selection a difficult task. We would like to express our thanks to the three invited speakers, Maxime Crochemore, Thomas Schwentick and Mihalis Yannakakis, for their contributions to the proceedings. Special thanks are due to A. Voronkov for his EasyChair software (www.easychair.org) which gives the organisers of conferences such as STACS a remarkable level of comfort; to Ralf Klasing for helping us explore the many possibilities of this brilliant software; to Emilka Bojanczyk for the design of the STACS poster, proceedings and logo; and to the members of the Organizing Committee, chaired by David Janin. An innovation in this year's STACS is the electronic format of the publication. A printed version was also available at the conference, with ISBN 978-3-939897-06-4. The electronic proceedings are available through several portals, and in particular through HAL and DROPS. HAL is an electronic repository managed by several French research agencies, and DROPS is the Dagstuhl Research Online Publication Server. We want to thank both these servers for hosting the proceedings of STACS and guaranteeing them perennial availability. The rights on the articles in the proceedings are kept with the authors and the papers are available freely, under a Creative Commons license (see www.stacs-conf.org/faq.html for more details).
Cite as

Susanne Albers and Pascal Weil. Preface -- 25th International Symposium on Theoretical Aspects of Computer Science. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:LIPIcs.STACS.2008.1326,
  author =	{Albers, Susanne and Weil, Pascal},
  title =	{{Preface -- 25th International Symposium on Theoretical Aspects of Computer Science}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{1--10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1326},
  URN =		{urn:nbn:de:0030-drops-13263},
  doi =		{10.4230/LIPIcs.STACS.2008.1326},
  annote =	{Keywords: Symposium, theoretical computer science, algorithms and data structures, automata and formal languages, computational and structural complexity, logic in computer science, applications}
}
Document
DOI: 10.4230/DagSemProc.05031.1
05031 Abstracts Collection – Algorithms for Optimization with Incomplete Information

Authors: Susanne Albers, Rolf H. Möhring, Georg Ch. Pflug, and Rüdiger Schultz

Published in: Dagstuhl Seminar Proceedings, Volume 5031, Algorithms for Optimization with Incomplete Information (2005)

Abstract
From 16.01.05 to 21.01.05, the Dagstuhl Seminar 05031 ``Algorithms for Optimization with Incomplete Information'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Susanne Albers, Rolf H. Möhring, Georg Ch. Pflug, and Rüdiger Schultz. 05031 Abstracts Collection – Algorithms for Optimization with Incomplete Information. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:DagSemProc.05031.1,
  author =	{Albers, Susanne and M\"{o}hring, Rolf H. and Pflug, Georg Ch. and Schultz, R\"{u}diger},
  title =	{{05031 Abstracts Collection  – Algorithms for Optimization with Incomplete Information}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--25},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.1},
  URN =		{urn:nbn:de:0030-drops-1948},
  doi =		{10.4230/DagSemProc.05031.1},
  annote =	{Keywords: Online optimization , robust optimization , stochastic programming , stochastic scheduling}
}
Document
DOI: 10.4230/DagSemProc.05031.2
05031 Summary – Algorithms for Optimization with Incomplete Information

Authors: Susanne Albers, Rolf H. Möhring, Georg Ch. Pflug, and Rüdiger Schultz

Published in: Dagstuhl Seminar Proceedings, Volume 5031, Algorithms for Optimization with Incomplete Information (2005)

Abstract
This paper summarizes the objectives and structure of a seminar with the same title, held from January 16th to 21th 2005 at Schloss Dagstuhl, Germany
Cite as

Susanne Albers, Rolf H. Möhring, Georg Ch. Pflug, and Rüdiger Schultz. 05031 Summary – Algorithms for Optimization with Incomplete Information. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:DagSemProc.05031.2,
  author =	{Albers, Susanne and M\"{o}hring, Rolf H. and Pflug, Georg Ch. and Schultz, R\"{u}diger},
  title =	{{05031 Summary – Algorithms for Optimization with Incomplete Information}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.2},
  URN =		{urn:nbn:de:0030-drops-1138},
  doi =		{10.4230/DagSemProc.05031.2},
  annote =	{Keywords: Online Optimization , Robust Optimization , Stochastic Programming , Stochastic Scheduling}
}
Document
DOI: 10.4230/DagSemProc.04091.1
04091 Abstracts Collection – Data Structures

Authors: Susanne Albers, Robert Sedgewick, and Dorothea Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 4091, Data Structures (2005)

Abstract
From 22.02. to 27.02.2004, Dagstuhl Seminar "Data Structures" was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar are put together in this paper. The first section describes the seminar topics and goals in general.
Cite as

Susanne Albers, Robert Sedgewick, and Dorothea Wagner. 04091 Abstracts Collection – Data Structures. In Data Structures. Dagstuhl Seminar Proceedings, Volume 4091, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:DagSemProc.04091.1,
  author =	{Albers, Susanne and Sedgewick, Robert and Wagner, Dorothea},
  title =	{{04091 Abstracts Collection – Data Structures}},
  booktitle =	{Data Structures},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4091},
  editor =	{Susanne Albers and Robert Sedgewick and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04091.1},
  URN =		{urn:nbn:de:0030-drops-1758},
  doi =		{10.4230/DagSemProc.04091.1},
  annote =	{Keywords: Cache oblivious algorithms , cell probe model , computational geometry , data compression , dictionaries , finger search , hashing , heaps I/O efficiency , lower bounds}
}
Document
DOI: 10.4230/DagSemRep.347
Online Algorithms (Dagstuhl Seminar 02271)

Authors: Susanne Albers, Amos Fiat, and Gerhard J. Woeginger

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Susanne Albers, Amos Fiat, and Gerhard J. Woeginger. Online Algorithms (Dagstuhl Seminar 02271). Dagstuhl Seminar Report 347, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{albers_et_al:DagSemRep.347,
  author =	{Albers, Susanne and Fiat, Amos and Woeginger, Gerhard J.},
  title =	{{Online Algorithms (Dagstuhl Seminar 02271)}},
  pages =	{1--20},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{347},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.347},
  URN =		{urn:nbn:de:0030-drops-152281},
  doi =		{10.4230/DagSemRep.347},
}
Document
DOI: 10.4230/DagSemRep.335
Data Structures (Dagstuhl Seminar 02091)

Authors: Susanne Albers, Robert Sedgewick, and Peter Widmayer

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Susanne Albers, Robert Sedgewick, and Peter Widmayer. Data Structures (Dagstuhl Seminar 02091). Dagstuhl Seminar Report 335, pp. 1-36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{albers_et_al:DagSemRep.335,
  author =	{Albers, Susanne and Sedgewick, Robert and Widmayer, Peter},
  title =	{{Data Structures (Dagstuhl Seminar 02091)}},
  pages =	{1--36},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{335},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.335},
  URN =		{urn:nbn:de:0030-drops-152176},
  doi =		{10.4230/DagSemRep.335},
}
Document
DOI: 10.4230/DagSemRep.267
Data Structures (Dagstuhl Seminar 00091)

Authors: Susanne Albers, Ian Munro, and Peter Widmayer

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Susanne Albers, Ian Munro, and Peter Widmayer. Data Structures (Dagstuhl Seminar 00091). Dagstuhl Seminar Report 267, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{albers_et_al:DagSemRep.267,
  author =	{Albers, Susanne and Munro, Ian and Widmayer, Peter},
  title =	{{Data Structures (Dagstuhl Seminar 00091)}},
  pages =	{1--22},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{267},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.267},
  URN =		{urn:nbn:de:0030-drops-151525},
  doi =		{10.4230/DagSemRep.267},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact